package jjn.round2;

/**
 * @author Jiang Jining
 * @since 2023-05-21 21:59
 */
public class Offer62_LastRemaining {
    public int lastRemaining(int n, int m) {
        return f(n, m);
    }
    
    private int f(int n, int m) {
        if (n == 1) {
            return 0;
        }
        int rest = f(n - 1, m);
        return (rest + m) % n;
    }
    
    public int lastRemainingV2(int n, int m) {
        int res = 0;
        for (int i = 2; i <= n; i++) {
            res = (res + m) % i;
        }
        return res;
    }
}
